package selection_sort;

public class sort {
    public static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    /*
     * 直接选择排序
     * 时间复杂度：O（n^2）
     * 空间复杂度：O（1）
     * 不稳定
     * */
    public static void directSelectionSort(int[] array){
//        for(int i=0;i<array.length;i++){
//            int temp=array[i];
//            int minIndex=i;
//            for(int j=i+1;j<array.length;j++){
//                if(array[j]<array[minIndex]){
//                    minIndex=j;
//                }
//            }
//            array[i]=array[minIndex];
//            array[minIndex]=temp;
//        }
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    /*
     * 双向选择排序
     * 时间复杂度
     * 空间复杂度
     * 稳定性：
     * */
    public static void selectSortTwoWay(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=right;
            for(int i=left+1;i<=right;i++){
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,minIndex,left);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }



    //创建大根堆
    public static void createHeap(int[] array){
        for(int parent =(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }
    //向下调整
    public static void siftDown(int[] array,int parent,int length){
        int child=2*parent+1;
        while(child<length){
            if(child+1<length && array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    /*
    * Heapsort 堆排序
    * 时间复杂度：O（N*logN）
    * 空间复杂度：O（1）
    * 稳定性：不稳定
    * */
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
}
